package linkedtable;

import java.util.HashSet;
import java.util.Set;

/**
 * @Description 141. 环形链表
 * @Author Firenut
 * @Date 2023-02-02 17:32
 */
public class T141_hasCycle {
    // 法1: 快慢指针
    public boolean hasCycle1(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode slow, fast;
        slow = head;
        fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) { //如果是环形链表,fast会在环里追上slow的
                return true;
            }
        }
        return false;
    }

    // 法2: 哈希表法
    public boolean hasCycle(ListNode head) {
        Set<ListNode> set=new HashSet<>();
        while(head!=null){
            if(set.contains(head)){
                return true;
            }
            set.add(head);
            head=head.next;
        }
        return false;
    }
}
